<?php
/**
 * AVL树是带有平衡条件的二叉查找树
 * 每个节点的左子树和右子树的高度最多差1
 */
class AvlTree extends BinarySearchTree
{
    /**
     * @var AvlNode $root 根节点
     */
    public $root=null;

    /**
     * 插入一个新数据
     * @param mixed $item
     * @return void
     */
    public function insert($item)
    {
        $node=AvlNode::create($item);
        if($this->root === null){
            $this->root=$node;
        }
        else{
            $this->root=$this->insertTo($node,$this->root);
        }
        $this->count++;
    }
    /**
     * 将一个节点插入到一个子树下
     * 递归调用
     * @param AvlNode $node
     * @param AvlNode $sup
     * @return AvlNode
     */
    protected function insertTo($node,$sup)
    {
        if($sup->data > $node->data){
            if($sup->left === null){
                $sup->left=$node;
            }
            else{
                $sup->left=$this->insertTo($node,$sup->left);
            }
        }
        else{
            if($sup->right === null){
                $sup->right=$node;
            }
            else{
                $sup->right=$this->insertTo($node,$sup->right);
            }
        }
        return $this->balanceNode($sup);
    }
    /**
     * 获取节点高度
     * 末端节点高度为0
     * 空节点返回-1
     * @param AvlNode $node
     * @return int
     */
    protected function height($node)
    {
        return $node ? $node->height : -1;
    }
    /**
     * 检查一个节点是否符合平衡条件
     * 如果不平衡则修复平衡
     * @param AvlNode $current
     * @return AvlNode
     */
    protected function balanceNode($current)
    {
        $left_height = $this->height($current->left);
        $right_height = $this->height($current->right);
        $diff=$left_height-$right_height;
        if($diff > 1){
            if($this->height($current->left->left) > $this->height($current->left->right)){
                $current=$this->leftSingleRotation($current);
            }
            else{
                $current=$this->leftDoubleRotation($current);
            }
        }
        elseif($diff < -1){
            if($this->height($current->right->left) < $this->height($current->right->right)){
                $current=$this->rightSingleRotation($current);
            }
            else{
                $current=$this->rightDoubleRotation($current);
            }
        }
        else{
            $current->height=max($left_height,$right_height)+1;
        }
        return $current;
    }
    /**
     * 左边单旋转
     * @param AvlNode $current
     * @return AvlNode
     */
    protected function leftSingleRotation($current)
    {
        $left=$current->left;
        $current->left=$left->right;
        $left->right=$current;
        $current->height=max($this->height($current->left),$this->height($current->right))+1;
        $left->height=max($this->height($left->left),$this->height($left->right))+1;
        return $left;
    }
    /**
     * 右边单旋转
     * @param AvlNode $current
     * @return AvlNode
     */
    protected function rightSingleRotation($current)
    {
        $right=$current->right;
        $current->right=$right->left;
        $right->left=$current;
        $current->height=max($this->height($current->left),$this->height($current->right))+1;
        $right->height=max($this->height($right->left),$this->height($right->right))+1;
        return $right;
    }
    /**
     * 左边双旋转
     * @param AvlNode $current
     * @return AvlNode
     */
    protected function leftDoubleRotation($current)
    {
        $current->left=$this->rightSingleRotation($current->left);
        return $this->leftSingleRotation($current);
    }
    /**
     * 右边双旋转
     * @param AvlNode $current
     * @return AvlNode
     */
    protected function rightDoubleRotation($current)
    {
        $current->right=$this->leftSingleRotation($current->right);
        return $this->rightSingleRotation($current);
    }
}
